package com.ai.zuochengyun.phase01.class03;

public class Code10_SmallerEqualBigger {
    public static void main(String[] args) {
        Node head = new Node(1);
        Node cur = head;
        int min = 1;
        int max = 1;
        System.out.print(1 + " ");
        for (int i = 0; i < 5; i++) {
            int rand = (int) (Math.random() * 10) + 1;
            min = Math.min(min, rand);
            max = Math.max(max, rand);
            Node node = new Node(rand);
            System.out.print(rand + " ");
            cur.next = node;
            cur = node;
        }
        System.out.println();
        int mid = min + ((max - min) >> 1);
        System.out.println("划分值：" + mid);

        Node node = listPartition2(head, mid);
        System.out.println("头节点的值：" + node.value);
        cur = node;
        while (cur != null) {
            System.out.print(cur.value + " ");
            cur = cur.next;
        }
    }

    /**
     * 将链表按值划分为小于，等于，大于的顺序
     *
     * @param head
     * @param pivot
     * @return
     */
    public static Node listPartition2(Node head, int pivot) {
        // 小于区的头节点和尾节点
        Node sH = null, sT = null;
        // 等于区的头节点和尾节点
        Node eH = null, eT = null;
        // 大于区的头节点和尾节点
        Node bH = null, bT = null;

        Node next = null;
        while (head != null) {
            // 记住下一个节点的位置
            next = head.next;
            // 需要将当前的节点和next节点之间断联
            head.next = null;
            if (head.value < pivot) {
                if (sH != null) {
                    // 之前的尾巴的next指向head
                    sT.next = head;
                    // 尾巴来到head
                    sT = head;
                } else {
                    sH = head;
                    sT = head;
                }
            } else if (head.value > pivot) {
                if (bH != null) {
                    // 之前的尾巴的next指向head
                    bT.next = head;
                    // 尾巴来到head
                    bT = head;
                } else {
                    bH = head;
                    bT = head;
                }
            } else {
                if (eH != null) {
                    // 之前的尾巴的next指向head
                    eT.next = head;
                    // 尾巴来到head
                    eT = head;
                } else {
                    // 头尾都指向当前节点
                    eH = head;
                    eT = head;
                }
            }
            head = next;
        }

        if (sT != null) {
            // 小于区的尾节点 串联 等于区的头节点
            sT.next = eH;
            // 下一步谁去串联大于区域的头节点，谁就是eT
            // 有等于区，那么就是等于区的尾节点 去串联 大于区的头节点
            // 无等于区，那么就是小于区的尾节点 去串联 大于区的头节点
            eT = eT == null ? sT : eT;
        }

        // 串联大于区的头节点
        if (eT != null) {
            eT.next = bH;
        }

        return sH != null ? sH : (eH != null ? eH : bH);
    }

    private static class Node {
        int value;
        Node next;

        public Node(int value) {
            this.value = value;
        }

        public Node next(Node next) {
            this.next = next;
            return this;
        }
    }

}
